const quickSortFunc = (arr) => {
    sort(arr, 0, arr.length - 1);
}

const sort = (arr, start, end) => {
    if(arr.length < 1 || start < 0 || end >= arr.length || start > end){
        return null;
    }
    // 数据分割成独立的两部分时，从哪的区分指示器
    let zoneIndex = partition(arr,start,end);
    if(zoneIndex > start){
        sort(arr,start,zoneIndex - 1);
    }
    if(zoneIndex < end){
        sort(arr,zoneIndex + 1, end);
    }
}

const partition = (arr, start, end) => {
    if(start === end) return start;
    // 选择中间的数值为中间点
    let pivot = Math.floor((start + end) / 2);
    let zoneIndex = start - 1;
    swap(arr, pivot, end);
    for (let i = start; i <= end; i++) {
        if(arr[i] <= arr[end]){
            zoneIndex++;
            if(i > zoneIndex){
                swap(arr, i, zoneIndex)
            }
        }
    }
    return zoneIndex;
}

const swap = (arr,pivot, end) => {
    let temp = arr[end];
    arr[end] = arr[pivot];
    arr[pivot] = temp;
}

let arr = [1,3,2,5,4,6,7,3];
quickSortFunc(arr);
console.log(arr);
